//二分查找
public class test10_16 {
	public int search(int[] nums, int target) {
		int right = 0;
		int left = nums.length-1;
		if(target<nums[0] || target>nums[nums.length-1]) {
			return -1;				//防止数据不在区间内还做寻找
		}
		while(right <= left) { 			 			//当left==right时区间[left, right]仍然有效
			int mid = right+((left-right) >> 1); 	//防止溢出，等同于 (right+left)/2。 虽然可以用“/”，不过 “>>” 貌似更快
			if(target == nums[mid]) {				//找到该数，返回下标
				return mid;
			} else if(target < nums[mid]) {
				left = mid-1;						//比中间值小，在左半边找
			} else {
				right = mid+1;						//比中间值大，在右半边找
			}
		}
		return -1;									//找不到，返回-1
	}


}
